package LL3;

public class Main {
    //定义链表节点
    static class CircularListNode {
        private int val;  //链表的数据域
        private CircularListNode next; //链表的指针域

        public CircularListNode(int val) {
            this.val = val; //链表的数据域
            this.next = null; //链表的指针域
        }
    }

    // 添加操作：给循环链表追加节点
    private static void Append(CircularListNode head, int val) {
        if (head == null) {
            return;
        }
        CircularListNode cur = head;
        //1. 移动指针变量到末尾节点
        while (cur.next != head) {
            cur = cur.next;
        }
        //2. 新节点追加到末尾节点
        CircularListNode newNode = new CircularListNode(val);
        cur.next = newNode;
        newNode.next = head; //更改末尾节点的指向
    }

    // 打印循环链表
    private static void Print(CircularListNode head) {
        if (head == null) {
            return;
        }
        CircularListNode cur = head.next;
        if (cur == head) {  //只有一个节点的情况
            System.out.println(cur.val);
            return;
        }

        //1. 打印头节点
        System.out.print(head.val + "\t");
        //2. 遍历打印其他节点
        while (cur != head) {
            System.out.print(cur.val + "\t");
            cur = cur.next;
        }
        System.out.println();
    }

    //删除操作，删除第k个节点（返回删除的节点）
    private static CircularListNode Remove(CircularListNode head, int k) {
        //head 为空 或者 只有1个节点
        if (head == null || head == head.next) {
            return head;
        }
        //情况1：删除的节点为头节点
        if (k == 0) {
            CircularListNode cur = head;
            //找到末尾节点
            while (cur.next != head) {
                cur = cur.next;
            }
            //更改末尾节点的指针域
            cur.next = head.next;
            return head;
        }
        //情况2：删除的节点为 非头节点
        CircularListNode cur = head;
        for (int i = 0; i < k - 1; i++) {
            cur = cur.next;
        }
        CircularListNode tmp = cur.next; //删除的节点
        cur.next = cur.next.next; //删除节点操作
        return tmp; //返回删除的节点
    }

    public static void josephus(int n, int m) {
        //1.  创建一个循环链表
        CircularListNode head = new CircularListNode(1);
        head.next = head; //构成一个环形链表
        //2.  添加节点
        for (int j = 1; j < n; j++) {
            Append(head, j + 1);
        }
        Print(head);
        //3. 依次删除链表节点
        for (int i = 0; i < n; i++) {
            CircularListNode removeNode = Remove(head, m - 1);
            System.out.print(removeNode.val + "\t");
            head = removeNode.next; //下次开始时，开始节点为删除节点的下一个节点
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // josephus(6, 5);
        //josephus(6, 1);
        josephus(41, 3);
    }
}